import java.util.Stack;

public class Sort {
    /**
    *直接插入排序
    *时间复杂度:
    *   最好情况->O(N)
    *   最坏情况->O(N^2)
    *空间复杂度:
    *       未创建新的空间O(1)
    *稳定性:稳定,不稳定的排序无法稳定,稳定的排序可以变得不稳定
     */
    public static void insertSort(int[] array) {
        //1.设计i,j下标,并把i下标对应的值赋值给tmp
        for(int i = 0;i < array.length;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0;j--) {
                //2.对tmp与j下标值进行比较,如果tmp小于i下标对应值的,则进行交换,直到j遍历完毕
                if(array[j] > tmp)  {
                    array[j + 1] = array[j];
                }else {
                    //array[j + 1] = tmp;//如果小于tmp,tmp返回i下标位置即可
                    break;
                }
            }
            //3.比较的内循环结束后,把tmp值赋给j+1位置
            array[j + 1] = tmp;
        }
    }
    /**
     * 希尔排序(缩小增量排序),不稳定排序
     */
    public static void shellSort(int[] array) {
        //1.获取增量gap
        int gap = array.length;
        //2.进行循环直接插入
        while(gap > 0) {
            gap /= 2;
            shell(array,gap);
        }
    }
    private static void shell(int[] array,int gap) {
        //直接插入
        for(int i = gap;i < array.length;i++) {
            int tmp = array[i];
            int j = i - gap;
            for(;j >= 0;j -= gap) {
                if(array[j] > tmp) {
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    /**
     * 选择排序
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     */
    public static void selectSort(int[] array) {
        //1.设计变量,i,j,并用min记录值
        for(int i = 0;i < array.length;i++) {
            int minIndex = i;
            for(int j = i + 1;j < array.length;j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
        //2.进行比较大小,保证每次确定一个排序
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void selectSort2(int[] array) {
        //1.设计i,minIndex,maxIndex,left,right
        int left = 0;
        int right = array.length - 1;
        //2.left首先放在头尾下标,i遍历数组,找到minIndex,maxIndex.并放到left,right
        while(left < right) {
            int i = left + 1;
            int minIndex = left;
            int maxIndex = left;
            while(i <= right ) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
                i++;
            }
            swap(array,left,minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    /**
     * 堆排序
     * 时间复杂度:
     * 空间复杂度:
     * 稳定性:
     */
    public static void heapSort(int[] array) {
        int end = array.length - 1;
        //1.创建大根堆
        createHeap(array);
        //2.头元素与最后一个元素进行交换
        while(end > 0) {
            swap(array,0,end);
            //3.向上调整,变为小根堆
            siftDown(array,0,end);
            end--;
        }
    }
    //创建大根堆
    private static void createHeap(int[] array) {
        //循环向上调整
        for(int parent = (array.length -1 - 1) / 2;parent >= 0;parent--) {
            siftDown(array,parent,array.length);
        }
    }
    //向上调整
    private static void siftDown(int[] array,int parent,int len) {
        int child = 2 * parent + 1;
        //1.找到父亲节点和子节点
        while(child < len ) {
            if(child + 1 < len && array[child] < array[child + 1]) {
                child = child + 1;
            }
            if(array[child]  > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
        //2.进行比较子节点左右节点大小
        //3.符合条件进行交换
    }
    /**
     * 冒泡排序
     * 最好情况,最坏情况O(N^2)
     * 稳定性:稳定
     */
    public static void  bubbleSort(int[] array) {
        for(int i = 0;i < array.length - 1;i++) {
            boolean flag = false;
            for(int j = 0;j < array.length - i - 1;j++) {
                if(array[j + 1] < array[j]) {
                    int tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                    flag = true;
                }
            }
            if(flag == false) {
                break;
            }
        }
    }
    /**
     * 快速排序
     * 时间复杂度:
     * 空间复杂度:
     * 稳定性:
     */
    public static void quickSort(int[] array) {
        quick(array,0,array.length - 1);
    }
    //快排
    private static void quick(int[] array,int start,int end) {
        //递归实现,当头尾相等||start > end 时,证明递归结束
        if(start >= end) {
            return;
        }
        //优化:
        //接近二叉树最后两层,进行直接插入排序
        if(end - start + 1 <= 19) {
            insertSort2(array,start,end);
            return;
        }
        //三数取中(把中间值放入left位置)
        int index = middleNum(array,start,end);
        swap(array,start,index);
        //1.传入头尾节点下标,使数组中左侧小于start,右侧大于start,并获得二次分割值
        int pivot = partition(array,start,end);//分割值
        //2.通过分割值,进行递归左右排序
        quick(array,start,pivot - 1);
        quick(array,pivot + 1,end);
    }
    //快速排序的直接插入
    private static void insertSort2(int[] array,int start,int end) {
        for(int i = start + 1;i <= end;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= start ;j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    //三数取中
    private static int middleNum(int[] array,int left,int right) {
        //1.找到中间值
        int mid = (left + right) / 2;
        //2.比较三个数,并返回三个数中间值
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    //分割寻找中间值,并使数组趋于整齐
    private static int partitionHoare(int[] array,int left,int right) {
        int tmp = array[left];//基准
        int i = left;//记录基准
        //1.循环比较
        while(left < right) {
            //寻找基准右侧值
            while(left < right && array[right] >= tmp) {
                right--;
            }
            //寻找基准左侧值
            while(left < right  && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }
    //挖坑法
    public static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while(left < right) {
            //1.找到大于基准值部分
            while(left < right && array[right] >= tmp) {
                right--;
            }
            //2.交换
            array[left] = array[right];
            //3.找到小于基准值部分
            while(left < right && array[left] <= tmp) {
                left++;
            }
            //4.交换
            array[right]  = array[left];
        }
        //5.基准插入
        array[left] = tmp;
        return left;
    }
    /**
     * 快排,非递归
     */
    public static void quickSortNor(int[] array)  {
        //1.首先先放入4个元素进入栈
        int left = 0;
        int right = array.length - 1;
        int pivot = partitionHoare(array,left,right);
        Stack<Integer> stack = new Stack<>();
        //2.出两个元素,赋值给left,right
        if(pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot + 1 < right) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        //3.再次进行分割,直到栈为空
        while(! stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partitionHoare(array,left,right);
            if(pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     * @param array
     */
    public static void mergeSort(int[] array) {
        mergeFunc(array,0,array.length - 1);
    }
    //归并方法
    private static void mergeFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = (right + left) / 2;
        //1.分解左右
        mergeFunc(array,left,mid);
        mergeFunc(array,mid +1,right);
        //2.合并左右
        merge(array,left,mid,right);
    }
    //并方法
    private static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] tmpArray = new int[right -left + 1];
        int k = 0;
        //1.一直比较s1,s2下标对应的值
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArray[k++] = array[s1++];
            }else {
                tmpArray[k++]  = array[s2++];
            }
        }
        //s2遍历完成,s1未完成
        while(s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        //s1遍历完成,s2未完成
        while(s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }
        //3.返回原来数组
        for(int i = 0;i < k;i++) {
            array[i + left] = tmpArray[i];
        }
    }

    /**
     * 归并非递归方法
     */
    public static void mergeSortNor(int[] array) {
        //1.设计gap(数组分为组个数),i(一组个数),left(一组最左值),right(一组最右值),mid(一组中间值)
        int gap = 1;
        while(gap < array.length) {
            //2.进行分解数组
            for(int i = 0;i < array.length;i = i + 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if(right >= array.length) {
                    right = array.length - 1;
                }
                //3.通过方法merge进行合并
                merge(array,left,mid,right);
            }
            gap = 2 * gap;
        }
    }
    /**
     * 计数排序
     * 时间复杂度:O(范围 + n)
     * 空间复杂度:O(范围)
     */
    public static void countSort(int[] array) {
        //1.找最值
        int min = array[0];
        int max = array[0];
        for(int i = 1;i < array.length;i++) {
            if(min > array[i]) {
                min = array[i];
            }

            if(max < array[i]) {
                max = array[i];
            }
        }
        //2.计数数组进行初始化
        int[] count = new int[max - min + 1];
        //3.遍历数组,把出现次数放入计数数组
        for(int i = 0;i < array.length;i++) {
            int index = array[i] - min;
            count[index]++;
        }

        int k = 0;
        //4.遍历计数数组,把出现次数值,放回到数组中
        for(int i = 0;i < count.length;i++) {
            while(count[i] != 0) {
                array[k] = i + min;
                k++;
                count[i]--;
            }
        }
    }
}
